class Node(object):
    def __init__(self, data=0):
        self.data = data
        self.next = None


class List(object):
    def __init__(self):
        self.head = Node()
        self.length = 0

    def findbefore(self, pos):
        before = self.head
        while pos > 0:
            before = before.next
            pos -= 1
        return before

    def insert(self, pos, data):
        assert 0 <= pos <= self.length
        # 断言：必须要满足才能只能后面的语句
        before = self.findbefore(pos)

        # insert data
        newNode = Node()
        newNode.data = data
        newNode.next = before.next
        before.next = newNode
        self.length += 1

    def remove(self, pos):
        assert pos < self.length

        before = self.findbefore(pos)
        if before.next is not None:
            before.next = before.next.next
            self.length -= 1

    def append(self, data):
        self.insert(self.length, data)

    def foreach(self):
        first = self.head.next
        while first is not None:
            yield first.data

            first = first.next

    # Change the value
    def alter(self, pos, data):
        assert 0 <= pos < self.length

        before = self.findbefore(pos)
        before.next.data = data

    def find(self, pos):
        before = self.findbefore(pos)
        return before.next.data

    def deleteByData(self, data):
        pos = 0
        first = self.head
        while True:
            if first.data != data:
                first = first.next
                pos += 1
            else:
                self.remove(pos-1)
                break


if __name__ == '__main__':
        l = List()
        l.append(4)
        l.append(5)
        l.insert(1, 89)
        l.alter(0, 93)
        for c in l.foreach():
            print(c)
        print('==============')
        l.deleteByData(5)
        for c in l.foreach():
            print(c)



